#include <iostream>
#include <string>
using namespace std;
#include <cctype>
//using namespace string;

class Solution 
{
public:
	string reverseOnlyLetters(string s) 
	{
		int len = s.size();
		string tmp;
		// 全翻转
		for (int i = 0; i < len; i++) 
		{
			tmp += s[len - 1 - i];
		}
		// 翻转s
		int j = 0;
		for (int i = 0; i < len; i++) 
		{
			if (isalpha(tmp[i]) != 0) 
			{
				while (isalpha(s[j]) == 0) 
				{
					j++;
				}
				s[j] = tmp[i];
				j++;
			}
		}
		
		return s;
	}
};

// 前后指针，交换
class Solution2 
{
public:
	string reverseOnlyLetters(string s) 
	{
		string::iterator left = s.begin();
		string::iterator right = s.end() - 1;
		char tmp = '\0';
//		两边一步一步走		
//		while (left < right)
//		{
//			if (isalpha(*left) != 0 && isalpha(*right) != 0)
//			{
//				char tmp = *left;
//				*left = *right;
//				*right = tmp;
//				++left;
//				--right;
//			}
//			else
//			{
//				if (isalpha(*left) == 0)
//				{
//					++left;
//				}	
//				if (isalpha(*right) == 0)
//				{
//					--right;
//				}
//			}
//		}
		
		// 快排的思想
		while (left < right)
		{
			// 左边先找到字母位置
			while (left < right && isalpha(*left) == 0)
			{
				left++;
			}
			
			// 右边找到字母位置
			while (left < right && isalpha(*right) == 0)
			{
				right--;
			}
			
			// 交换
			tmp = *left;
			*left = *right;
			*right = tmp;
			++left;
			--right;
		}
			
		
		
		return s;
	}
};

int main()
{
	string s1("ab-cd");
	Solution exe;
	cout << exe.reverseOnlyLetters(s1) << endl;
	cout << s1 << endl;
	
	string s2("ab-cd");
	Solution2 exe2;
	cout << exe2.reverseOnlyLetters(s2) << endl;
	cout << s2 << endl;
	
//	string s;
//	s += "aaaaaa";
//	cout << s << endl;
	
//	cout << typeid(string::iterator).name();
	
	return 0;
}
